
/**
 * 给定二维数组，每一行取一个格子获取权值
 * 但相邻两行如果分别选取c1和c2的话，总得分需要减少abs(c1-c2)
 * 求最大得分
 * 令Dij为以（i，j）为终点的最大分数
 * Dij = Aij + max(D[i+1][k] - abs(j - k))
 * 去除绝对值符号
 * Dij = Aij + max(D[i+1][k] + k - j) k在j左边
 *  或 = Aij + max(D[i+1][k] - k + j) k在j右边
 * 注意到对于本式子j是常数，所以
 * 
 *   Dij = Aij - j + max(D[i+1][k] + k) k在j左边
 *       = Aij + j + max(D[i+1][k] - k) k在j右边
 *   
 *  对于第一种情况只需要从左向右扫描一遍，时刻维护最大的 D[i+1][k] + k 即可
 *  第二种情况从右向左即可
 */

using llt = long long;
using vll = vector<llt>;
const llt None = -0x7F8F9FAFBFCFDFEF;
int N, M;
vector<vll> D;

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        N = points.size();
        // if(1 == N) return *max_element(points[0].begin(), points[0].end());

        M = points[0].size();
        D.assign(N, vll(M, None));

        for(int i=0;i<M;++i){
            D[N - 1][i] = points[N - 1][i];
        }

        for(int i=N-2;i>=0;--i){
            // 从左向右
            llt mmax = D[i + 1][0];
            for(int j=0;j<M;++j){
                mmax = max(mmax, D[i + 1][j] + j);
                D[i][j] = points[i][j] - j + mmax;
            }
            // 再求Fij
            mmax = D[i + 1][M - 1] - (M - 1);
            for(int j=M-1;j>=0;--j){
                mmax = max(mmax, D[i + 1][j] - j);
                auto tmp = points[i][j] + j + mmax;
                D[i][j] = max(D[i][j], tmp);
            }
        }
        return *max_element(D[0].begin(), D[0].end());
    }
};
